package demo2;

public class TestHeap {
    int[] elem;
    int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    //建堆(通过向上调整 O(n))
    public void createHeap() {
        for (int i = 0; i < elem.length; i++) {
            shiftUp(i);
        }
    }
    //向上调整
    public void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while(child > 0) {
            if (elem[parent] < elem[child]) {
                swap(parent,child);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    //堆排序 --> 由小到大
    //空间复杂度 : o(1)
    //时间复杂度 :n*logn
    public void heapSort() {
        int end = usedSize - 1;
        //交换堆顶与堆尾元素
        for (int i = end; i > 0;) {
            swap(0,i);
            i--;
            //交换完后向下调整
            shiftDown(0,i);
        }
    }
    //向下调整
    public void shiftDown(int parent, int end) {
        int child = (parent * 2) + 1;
        while(child <= end) {
            if ((child + 1 <= end) && (elem[child + 1] > elem[child])) {
                child++;
            }
            if (elem[parent] < elem[child]) {
                swap(parent,child);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    //交换
    public void swap(int x, int y) {
        int temp = elem[x];
        elem[x] = elem[y];
        elem[y] = temp;
    }
}
